1. Technical Field
The present invention relates to congestion management of information in computer systems and/or communications networks.
2. Prior Art
The use of flow control mechanisms and techniques for managing congestion in computer networks are well known in the prior art. The mechanisms and techniques are necessary to ensure that quality of service (QoS) obligations are maintained at all times including periods of congestion in the network. The QoS obligations are Service Level Contracts (SLC) between service providers and customers in which the customer pays and is promised (by the service provider) that the customer's data will have certain level of throughput in the network. Failure to provide the agreed upon throughput could result in the provider paying damages for breach of the SLC. To prevent this undesirable result, there is always a desire and need to provide more effective and efficient flow control mechanisms and methods.
In order to manage data and provide for QoS the flow control management is implemented in network devices (such as servers, routers, bridges, adapters, etc.) In particular data packets are placed into pipes or flows. The flow control management (device and method) control the rate at which data packets are moved from flows into a service queue for further processing.
A common prior art flow control of packets in computer networks is called Random Early Detection (RED). This function is positioned to be effective as packets arrive. A packet is called transmitted if the decision of flow control is to enqueue it in a buffer to await processing. A packet is called discarded if the decision of flow control is to delete it. Queue occupancy can be expressed as a fraction of total capacity; so 0 represents no packets awaiting processing and 1 represents complete use of the buffer to store packets. As queue length in the buffer grows from 0 to a threshold Lo>=0, RED at first transmits all packets into the queue. As queue occupancy exceeds Lo and increases further, a decreasing fraction of packets is transmitted into the queue. Finally, if occupancy reaches or exceeds a threshold Hi<=1, RED completely discards all arriving packets. In general 0<=Lo<=Hi <=1. The value of queue length in the buffer relative to these thresholds determines whether RED transmits or discards offered packets. For queue occupancy Q that is between Lo and Hi, the fraction T of packets transmitted can be a linear function of the following form:T(Q)=1−(1−Tmin)*(Q−Lo)/(Hi−Lo); where * represents multiplication operator.Here Tmin is a minimum transmitted fraction reached as Q increases to Hi. Many variations on this theme are practiced in the prior art; for example, Q might actually be an exponentially weighted moving average of queue occupancy. As another example, Lo=Hi, the special case known as taildrop flow control. That is, taildrop flow control calls for transmitting all packets if Q is less than Lo=Hi, otherwise transmitting no packets.
The use of multiple thresholds (weights) is called Weighted RED (WRED).
The use of RED or WRED (including many variants) unfortunately can imply some undesirable consequences including:
1. RED and WRED ignore rate of change of queue (queue going up, down)
2. High thresholds can cause high latency and lack of headroom for bursts
3. Low thresholds can cause burst-shaving (low utilization)
4. There is no direct relationship between thresholds and performance.
5. Administrative input can be needed to retune thresholds as offered loads change.
6. Hand-tuning thresholds is widely recognized as difficult.
7. Little or no guidance appears in vendor documents.
8. Bandwidth allocation for hierarchies of bandwidth limits cannot be easily provided.
9. Bandwidth allocation that respects priority cannot be easily provided.
A drawback of prior art techniques is that the decision to transmit or discard an arriving packet is made in the device based upon heuristically determined threshold or functions. A queue threshold has little or nothing to do with key characteristics of flows. Threshold flow control systems can also be subject to high queueing latency during even a small degree of oversubscription. In addition, the threshold has to be tuned manually. Another drawback with the prior art techniques is that they can control a relatively small number of flows. However, there are several applications in which the flow control management is called upon to manage thousands of pipes or flows.
In view of the above RED or WRED does not give a network administrator sufficient control to manage a computer network efficiently. As a consequence a system and method are required to provide the necessary control.